﻿
package extremefx.collections {
	import extremefx.conditions.requires;	
	import extremefx.conditions.requiresNumber;	
	import extremefx.ICloneable;
	import extremefx.IComparer;
	import extremefx.IEnumerable;
	import extremefx.IEnumerator;
	import extremefx.collections.ICollection;
	import extremefx.collections.IList;
	
	import flash.net.registerClassAlias;
	import flash.utils.IDataInput;
	import flash.utils.IDataOutput;
	import flash.utils.Proxy;

	/**
	 * @author Marcelo Volmaro
	 * Implements the IList interface using an array whose size is dynamically increased as required.
	 */
	 
	public final class ArrayList extends Proxy implements IList, ICloneable, ICollection, IEnumerable {
		registerClassAlias("extremefx.collections.ArrayList", ArrayList);
		
    	private var _size:uint; 
    	private var _list:Array;
    	
    	/**
    	 * Initializes a new instance of the ArrayList class that contains elements copied from the specified collection and that has the same initial capacity as the number of elements copied. 
    	 */
		public function ArrayList(pCol:* = null) {
			clear();
			
			if(pCol is ICollection) {
				_list = ICollection(pCol).toArray();
				_size = _list.length;
				
			} else if (pCol is Array){
				_list = (pCol as Array).concat();
				_size = _list.length;
			}
		}
		
		public function getEnumerator():IEnumerator {
			return new NativeArrayEnum(_list);
		}
	    
	    public function getAt(pIndex:uint):* {
	    	requiresNumber(pIndex, "pIndex").isLessThan(_size);
	    	return _list[pIndex];
	    }
	    
	    public function setAt(pIndex:uint, pVal:*):void {
	    	requiresNumber(pIndex, "pIndex").isLessThan(_size);
			_list[pIndex] = pVal;
	    }
		
		/**
		 * Inserts an element into the ArrayList at the specified index.
		 * @param pIndex The zero-based index at which pObject should be inserted.
		 * @param pObject The Object to insert. The value can be a null reference. 
		 */
		public function insert(pIndex:uint, pObject:*):void {
			_rangeCheck(pIndex);
			var s:Array = _list.slice(0, pIndex);
			var e:Array = _list.slice(pIndex);
			_list = s.concat(pObject).concat(e);
			_size = _list.length;
		}
		
		/**
		 * Removes the element at the specified index of the ArrayList.
		 * @param pIndex The zero-based index of the element to remove.
		 */
		public function removeAt(pIndex:uint):void {
			_rangeCheck(pIndex, 1);
			_list.splice(pIndex, 1);
			_size = _list.length; 
		}
		
		/**
		 * Removes a range of elements from the ArrayList.
		 * @param pIndex The zero-based starting index of the range of elements to remove.
		 * @param pLength The number of elements to remove.
		 */
		public function removeRange(pIndex:uint, pLength:uint):void {
			_rangeCheck(pIndex, pLength);
			_list.splice(pIndex, pLength);
			_size = _list.length; 
		}
		
		/**
		 * Reverses the order of the elements in the ArrayList or a portion of it.
		 * @param pIndex The zero-based starting index of the range to reverse.
		 * @param pLength The number of elements in the range to reverse.
		 */
		public function reverse(pIndex:uint = 0, pLength:uint = uint.MAX_VALUE):void {
			if (pLength == uint.MAX_VALUE) pLength = _size - pIndex;
			_rangeCheck(pIndex, pLength);
			
			var to:uint = pIndex+pLength-1;
			var loops:uint = uint(pLength/2);
			var tmp:Object;
			var from:uint = pIndex;
			
			for (var i:uint = 0; i < loops; i++) {
				tmp = _list[from];
				_list[from++] = _list[to];
				_list[to--] = tmp;
			}
		}
		
		/**
		 * Searches for the specified Object and returns the zero-based index of the first occurrence within the range of elements in the ArrayList that extends from the specified index to the last element. 
		 * @param pObject The Object to locate in the ArrayList. The value can be a null reference.
		 * @param pStart The zero-based starting index of the search.
		 * @return The zero-based index of the first occurrence of value within the range of elements in the ArrayList that extends from pStart to the last element, if found; otherwise, -1. 
		 */
		public function indexOf(pObject:*, pStart:uint = 0):int {
			return _list.indexOf(pObject, pStart); 
		}
		
		/**
		 * Searches for the specified Object and returns the zero-based index of the last occurrence within the range of elements in the ArrayList that extends from the first element to the specified index. 
		 * @param pObject The Object to locate in the ArrayList. The value can be a null reference.
		 * @param pStart The zero-based starting index of the backward search. 
		 * @return The zero-based index of the last occurrence of value within the range of elements in the ArrayList that extends from the first element to startIndex, if found; otherwise, -1. 
		 */
		public function lastIndexOf(pObject:*, pStart:uint = uint.MAX_VALUE):int {
			return _list.lastIndexOf(pObject, pStart);
		}
		
		/**
		 * Creates a shallow copy of the ArrayList.
		 * @return A shallow copy of the ArrayList.
		 */
		public function clone():Object {
			return new ArrayList(this);
		}
		
		/**
		 * Adds an object to the end of the ArrayList.
		 * @param pObject The Object to be added to the end of the ArrayList. The value can be a null reference.
		 * @return The ArrayList index at which the value has been added.
		 */
		public function add(pObject:*):uint {
			_list[_size] = pObject;
      		return _size++;
		}
		
		/**
		 * Removes all elements from the ArrayList.
		 */
		public function clear():void {
			_list = new Array();
			_size = 0;
		}
		
		/**
		 * Determines whether an element is in the ArrayList.
		 * @param pObject The Object to locate in the ArrayList. The value can be a null reference.
		 * @return true if item is found in the ArrayList; otherwise, false.
		 */
		public function contains(pObject:*):Boolean {
			return -1 < _list.indexOf(pObject); 
		}
		
		/**
		 * Inserts the elements of a collection into the ArrayList at the specified index.
		 * @param pIndex The zero-based index at which the new elements should be inserted.
		 * @param pCollection The ICollection whose elements should be inserted into the ArrayList. The collection itself cannot be a null reference, but it can contain elements that are a null reference.
		 */
		public function insertRange(pIndex:uint, pCollection:ICollection):void {
			_rangeCheck(pIndex);
			requires(pCollection, "pCollection").isNotNull();
			
		    var s:Array = _list.slice(0, pIndex);
			var e:Array = _list.slice(pIndex);
			_list = s.concat(pCollection.toArray()).concat(e);
		    _size = _list.length;
		}
		
		/**
		 * Removes the first occurrence of a specific object from the ArrayList.
		 * @param pObject The Object to remove from the ArrayList. The value can be a null reference.
		 */
		public function remove(pObject:*):void {
			var x:int = _list.indexOf(pObject);
			if (-1 < x) removeAt(x);
		}
		
		/**
		 * Gets the number of elements actually contained in the ArrayList.
		 * @return The number of elements actually contained in the ArrayList.
		 */
		public function get count():uint {
			return _size; 
		}
		
		/**
		 * Copies the ArrayList or a portion of it to a standard flash Array.
		 * @param pIndex The zero-based index in the source ArrayList at which copying begins.
		 * @param pCount The number of elements to copy. 
		 */
		public function toArray():Array {
			return _list.concat();
		}
		
		/**
		 * Copies the elements of a collection over a range of elements in the ArrayList.
		 * @param pIndex The zero-based ArrayList index at which to start copying the elements of pCollection.
		 * @param pCollection The ICollection whose elements to copy to the ArrayList. The collection itself cannot be a null reference, but it can contain elements that are a null reference.
		 */
		public function setRange(pIndex:uint, pCollection:ICollection):void {
			_rangeCheck(pIndex);
			
			requires(pCollection, "pCollection").isNotNull();
			
		    var s:Array = _list.slice(0, pIndex);
			_list = s.concat(pCollection.toArray());
		    _size = _list.length;
		}
		
		/**
		 * Returns an ArrayList whose elements are copies of the specified value.
		 * @param pObject The Object to copy multiple times in the new ArrayList. The value can be a null reference.
		 * @param pCount The number of times value should be copied.
		 * @return An ArrayList with count number of elements, all of which are copies of value.
		 */
		public static function repeat(pObject:*, pCount:uint):ArrayList {
			var a:ArrayList = new ArrayList();
			while (pCount--){
				a.add(pObject);
			}
			
			return a;
		}
		
		public function equals(pObject:*):Boolean {
			return (pObject === this);
		}
		
		/**
		 * Searches a range of elements in the sorted ArrayList for an element using the specified comparer and returns the zero-based index of the element.
		 * @param pObject The Object to locate. The value can be a null reference.
		 * @param pComparer The IComparer implementation to use when comparing elements or null to use the default comparer that is the IComparable implementation of each element.
		 * @param pIndex The zero-based starting index of the range to search.
		 * @param pCount The length of the range to search.
		 * @return The zero-based index of value in the sorted ArrayList, if value is found; otherwise, a negative number, which is the bitwise complement of the index of the next element that is larger than value or, if there is no larger element, the bitwise complement of count.
		 */
		public function binarySearch(pObject:*, pComparer:IComparer = null, pIndex:uint = 0, pCount:uint = uint.MAX_VALUE):int{
			if (pCount == uint.MAX_VALUE) pCount = _size;
			_rangeCheck(pIndex, pCount);
			
			var r:int, x:int, y:int, z:int; 
			
			if (pComparer == null) pComparer = new Comparer();
			
			x = pIndex;
			y = pIndex + pCount - 1;
			
			while (x <= y) {
				z = x + ((y - x) / 2);
				r = pComparer.compare(pObject, _list[z]);
				
				if (r < 0) {
					y = z - 1;
					
				} else if (r > 0) {
					x = z + 1;
					
				} else {
					return z;
				}
			}

			return ~x;
		}
		
		/**
		 * Sorts the elements in a range of elements in ArrayList using the specified comparer.
		 * @param pComparer The IComparer implementation to use when comparing elements or a null reference to use the IComparable implementation of each element. 
		 * @param pIndex The zero-based starting index of the range to sort.
		 * @param pCount The length of the range to sort.
		 */
		public function sort(pComparer:IComparer = null, pIndex:uint = 0, pCount:uint = uint.MAX_VALUE):void {
			if (pCount == uint.MAX_VALUE) pCount = _size;
			if (pComparer == null) pComparer = new Comparer();
			
			if (pIndex == 0 && pCount == _size) {
				_list.sort(pComparer.compare);// Does not support indexes...
				
			} else {
				_rangeCheck(pIndex, pCount);
				_quickSort(_list, pIndex, pIndex + pCount - 1, pComparer);
			}
		}
		
		private function _quickSort(pList:Array, pLeft:uint, pRight:uint, pComparer:IComparer):void {
			var i:uint, j:uint, middle:uint, pivot:*;
					
			if (pLeft >= pRight) {
				return;
			}

			middle = pLeft + ((pRight - pLeft) / 2);

			if (pComparer.compare(pList[middle], pList[pLeft]) < 0) {
				_swap(pList, middle, pLeft);
			}

			if (pComparer.compare(pList[pRight], pList[pLeft]) < 0) {
				_swap(pList, pRight, pLeft);
			}

			if (pComparer.compare(pList[pRight], pList[middle]) < 0) {
				_swap(pList, pRight, middle);
			}
	
			if (pRight - pLeft + 1 <= 3) {
				return;
			}
	
			_swap(pList, pRight - 1, middle);
			pivot = pList[pRight - 1];
			i = pLeft;
			j = pRight - 1;			
	
			while (true) {
				while (pComparer.compare(pList[++i], pivot) < 0);
				while (pComparer.compare(pList[--j], pivot) > 0);
		
				if (i < j) {
					_swap(pList, i, j);
					
				} else {
					break;
				}
			}

			_swap(pList, pRight - 1, i);
			_quickSort(pList, pLeft, i - 1, pComparer);
			_quickSort(pList, i + 1, pRight, pComparer);	
		}
		
		private static function _swap(pList:Array, pX:uint, pY:uint):void {
			var tmp:* = pList[pX];
			pList[pX] = pList[pY];
			pList[pY] = tmp;
		}
		
		/**
		 * Returns an ArrayList which represents a subset of the elements in the source ArrayList.
		 * @param pIndex The zero-based ArrayList index at which the range starts.
		 * @param pLength The number of elements in the range.
		 * @return An ArrayList which represents a subset of the elements in the source ArrayList.
		 */
		public function getRange(pIndex:uint = 0, pLength:uint = 16777215):ArrayList{
			var a:ArrayList = new ArrayList();
			a._list = _list.slice(pIndex, pIndex+pLength);
			a._size = a._list.length;
			return a;
		}

		private function _rangeCheck(pIndex:uint, pLength:uint = uint.MAX_VALUE):void {
			requiresNumber(pIndex, "index").isLessThan(_size);
			
			if (pLength != 0 && pLength != uint.MAX_VALUE) {
				pIndex += pLength-1;
				requiresNumber(pIndex, "length").isLessThan(_size);
			}
		}
		
		public function readExternal(input:IDataInput):void {
			_list = input.readObject();
			_size = input.readUnsignedInt();
		}
		
		public function writeExternal(output:IDataOutput):void {
			output.writeObject(_list);
			output.writeUnsignedInt(_size);
		}
	}
}